DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2023.14

Proofs of Proof-Of-Stake with Sublinear Complexity

Authors: Shresth Agrawal, Joachim Neu, Ertem Nusret Tas, and Dionysis Zindros

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract

Popular Ethereum wallets (like MetaMask) entrust centralized infrastructure providers (e.g., Infura) to run the consensus client logic on their behalf. As a result, these wallets are light-weight and high-performant, but come with security risks. A malicious provider can mislead the wallet by faking payments and balances, or censoring transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but are concretely inefficient, often with asymptotically linear bootstrapping complexity. This poses a dilemma between decentralization and performance. We design, implement, and evaluate a new proof-of-stake (PoS) superlight client with concretely efficient and asymptotically logarithmic bootstrapping complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree of PoS epochs. The verifier enrolls the provers in a bisection game, in which honest provers are destined to win once an adversarial Merkle tree is challenged at sufficient depth. We provide an implementation for mainnet Ethereum: compared to the state-of-the-art light client construction of Ethereum, our client improves time-to-completion by 9×, communication by 180×, and energy usage by 30× (when bootstrapping after 10 years of consensus execution). As an important additional application, our construction can be used to realize trustless cross-chain bridges, in which the superlight client runs within a smart contract and takes the role of an on-chain verifier. We prove our construction is secure and show how to employ it for other PoS systems such as Cardano (with fully adaptive adversary), Algorand, and Snow White.

Cite as

Shresth Agrawal, Joachim Neu, Ertem Nusret Tas, and Dionysis Zindros. Proofs of Proof-Of-Stake with Sublinear Complexity. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.AFT.2023.14,
  author =	{Agrawal, Shresth and Neu, Joachim and Tas, Ertem Nusret and Zindros, Dionysis},
  title =	{{Proofs of Proof-Of-Stake with Sublinear Complexity}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.14},
  URN =		{urn:nbn:de:0030-drops-192037},
  doi =		{10.4230/LIPIcs.AFT.2023.14},
  annote =	{Keywords: Proof-of-stake, blockchain, light client, superlight, bridge, Ethereum}
}

Document

DOI: 10.4230/LIPIcs.AFT.2023.29

Vector Commitments with Efficient Updates

Authors: Ertem Nusret Tas and Dan Boneh

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract

Dynamic vector commitments that enable local updates of opening proofs have applications ranging from verifiable databases with membership changes to stateless clients on blockchains. In these applications, each user maintains a relevant subset of the committed messages and the corresponding opening proofs with the goal of ensuring a succinct global state. When the messages are updated, users are given some global update information and update their opening proofs to match the new vector commitment. We investigate the relation between the size of the update information and the runtime complexity needed to update an individual opening proof. Existing vector commitment schemes require that either the information size or the runtime scale linearly in the number k of updated state elements. We construct a vector commitment scheme that asymptotically achieves both length and runtime that is sublinear in k, namely k^ν and k^{1-ν} for any ν ∈ (0,1). We prove an information-theoretic lower bound on the relation between the update information size and runtime complexity that shows the asymptotic optimality of our scheme. While in practice, the construction is not yet competitive with Verkle commitments, our approach may point the way towards more performant vector commitments.

Cite as

Ertem Nusret Tas and Dan Boneh. Vector Commitments with Efficient Updates. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tas_et_al:LIPIcs.AFT.2023.29,
  author =	{Tas, Ertem Nusret and Boneh, Dan},
  title =	{{Vector Commitments with Efficient Updates}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.29},
  URN =		{urn:nbn:de:0030-drops-192184},
  doi =		{10.4230/LIPIcs.AFT.2023.29},
  annote =	{Keywords: Vector commitments, stateless clients}
}

Search Results

Documents authored by Tas, Ertem Nusret

Proofs of Proof-Of-Stake with Sublinear Complexity

Abstract

Cite as

Vector Commitments with Efficient Updates

Abstract

Cite as

Thanks for your feedback!

Could not send message